#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 核心思路：哈希表+二分查找 适配大量s查询的进阶场景 大幅提升查询效率
    // 1. 预处理字符串t 构建哈希表映射关系
    //    哈希表的key为t中的单个字符 value为该字符在t中出现的所有索引组成的有序列表
    //    因t是顺序遍历 索引列表天然按从小到大排序 为后续二分查找奠定基础
    // 2. 初始化prevIndex为-1 用于记录s中前一个字符在t中匹配到的索引位置
    //    确保s中字符在t中的匹配顺序保持一致 满足子序列相对位置不变的要求
    // 3. 遍历s中的每个字符 逐个验证能否在t中找到合法匹配位置
    //    a 首先检查当前字符是否存在于哈希表中 若不存在说明t中无该字符 s不可能是子序列 直接返回false
    //    b 若存在 取出该字符对应的所有索引列表
    //    c 利用lower_bound函数进行二分查找 目标是找到索引列表中第一个大于prevIndex的索引
    //      lower_bound返回第一个大于等于目标值的元素迭代器 此处目标值设为prevIndex+1 恰好满足"大于prevIndex"的需求
    //    d 检查二分查找结果 若迭代器等于索引列表的end 说明没有找到符合条件的索引 即当前字符在t中的所有出现位置都在之前匹配字符之前 s不是子序列 直接返回false
    //    e 若找到合法索引 更新prevIndex为该索引值 继续遍历s的下一个字符
    // 4. 若s中所有字符都成功找到符合条件的匹配位置 说明s是t的子序列 返回true
    bool isSubsequence(string s, string t) {
        unordered_map<char, vector<int>> map;
        for (int i = 0; i < t.size(); i++) {
            map[t[i]].push_back(i);
        }

        int prevIndex = -1; // 记录上一个匹配字符在 t 中的索引
        for (auto e : s) {
            if (map.find(e) == map.end()) {
                return false;
            }

            const vector<int> index = map[e];
            // 用二分查找找第一个大于 prevIndex 的索引（保证相对位置）
            auto it = lower_bound(index.begin(), index.end(), prevIndex + 1);

            // 找不到符合条件的索引，说明 s 不是子序列
            if (it == index.end()) {
                return false;
            }
            // 更新 prevIndex 为当前找到的索引
            prevIndex = *it;
        }

        return true;
    }
};